Electronic commerce plays an increasingly important role in modern society and necessarily involves the transmission of electronic data between two parties. In a commercial environment, a first party may wish to transmit electronic data to a second party over an intervening communications network, in particular the internet, only when confident that there is adequate security against eavesdroppers that may be present on the network. The parties may be computer entities, for example.
One way to achieve this is for the first party to encrypt the data in a manner that only the second party can decrypt after receipt. One class of such encryption techniques, and with which the present invention is concerned, is public-key cryptography based on the computational difficulty of factoring large integers. The first party encrypts a message by use of a public-key published by the second party the crypted message only being practicably decrypted by use of corresponding private components of the key held by the second party. These techniques include the well-known RSA cryptosystem, for example.
In many cases, the first party will not wish to use the encryption system without being confident that the public-key to be used to encrypt the data conforms to an agreed set of criteria related to the security of the encryption to be obtained. One way to achieve this is to seek a certificate from a trusted certification authority that has verified to its own satisfaction that the public-key does so conform. An alternative way is for the first party to seek verification directly from the second party. Whatever the route to verification, the owner of the public-key generally prefers, and it is often a requirement of the encryption standard adopted, that the proof that the public-key is as it is claimed is achieved without revealing the private component to the verifier. That is, the proving party runs what is called a protocol with the verifying party that provides a ‘knowledge proof’ of the validity of the private components. For instance, the ISO standardization document 9798 part 3 recommends that public-key certification include knowledge proof for possession of the private component that matches the pubic key to be certified.
An example of such a set of criteria known to provide a highly secure public-key is that the public-key is an integer (n) which is the product of only two odd primes (p,q) and that the primes have lengths in bits which differ by no more than a predetermined value, d, commonly equal to 2.
Given the computational intractability of factoring large integers, there exists no known algorithm that can be input a given number n and terminate in a polynomial time in the size of n with an output answering whether n is the product of exactly two odd primes. Nevertheless, there do exist practically efficient interactive protocols that run in polynomial time and allow a prover who knows the factorization of n to prove such a structure to the satisfaction of a verifier without disclosing the factorization information to the latter.
An early idea for proving n in such a structure is based on an observation due to Adleman [see R. Berger, S. Kannan and R. Peralta. A framework for the study of cryptographic protocols, Advances in Cryptology—Proceedings of CRYPTO 85 (H. C. Williams ed.), Lecture Notes in Computer Science, Springer-Verlag 218 (1986), pp. 87–103]. He suggested using the fact that if n has exactly two different prime factors (which may include their powers) then exactly a quarter of the elements in the multiplicative group mod n are quadratic residues (square numbers of n). On the other hand, if n has more than two prime factors then at most one-eighth of them are quadratic residues. Thus a prover, knowing the factorization of n, can show a verifier the structure via binomial trials that for a set of k elements randomly chosen from the multiplicative group mod n, roughly k/4 of them are quadratic residues (shown by disclosing to the verifier their square roots). Using a normal distribution as an approximation to the probability of binomial trials (a standard method), Berger et al [R. Berger, S. Kannan and R. Peralta. A framework for the study of cryptographic protocols, Advances in Cryptology—Proceedings of CRYPTO 85 (H. C. Williams ed.), Lecture Notes in Computer Science, Springer-Verlag 218 (1986), pp. 87–103] established that if                     21            -      1        20    ⁢  kor more such elements are shown to be quadratic residues then the proof should be accepted with the probability of error between e−k/74 and e−k/75. Thus, k should be in thousands (k=3000 was suggested in [R. Berger, S. Kannan and R. Peralta. A framework for the study of cryptographic protocols, Advances in Cryptology—Proceedings of CRYPTO 85 (H. C. Williams ed.), Lecture Notes in Computer Science, Springer-Verlag 218 (1986), pp. 87–103]) in order for the error probability to be negligibly small. (We note e−3000/74<½58<e−3000/75 and regard an amount at this level to be negligibly small). Since the cost for computing a square root mod n is measured by O(log2n) multiplications of integers mod n, the total cost for proving the two-prime-product structure of a number n by showing quadratic residue information will be O(k log2n) (multiplications mod n) with an error probability between e−k/74 and e−k/75.
Van de Graaf and Peralta [J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public-key, Advances in Cryptology—Proceedings of CRYPTO 87 (E. Pomerance, ed.), Lecture Notes in Computer Science, Springer-Verlag 293 (1988), pp. 128–134] observed that if n is a Blum integer, that is, n is the product of two distinct prime factors (again this may include their powers), both congruent to 3 mod 4, then any element in the multiplicative group mod n with the positive Jacobi symbol has the property that either itself or its negation is a quadratic residue modulo n. Their protocol for proof of Blum integer is based on this fact. A number of other previous protocols for proving two-prime-product structure also use this idea (e.g., [J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes, In Advances in Cryptology—EUROCRYPT 99, Lecture Notes in Computer Science, Springer-Verlag 1592 (1999), pp. 106–121, R. Gennaro, D. Miccianicio and T. Rabin. An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, In 5th ACM Conference on Computer and Communications Security, October 1998, M. Liskov and R. D. Silverman. A statistical limited-knowledge proof for secure RSA keys, IEEE P1363 Research Contributions]). Note that provided n is not a square number (which is easy to test against), exactly half of the elements in the multiplicative group mod n can have a positive Jacobi symbol which is also easy to evaluate. Thus, given such n, the above demonstration actually shows that a quarter of elements in the group are quadratic residues (since a quadratic residue must have positive Legendre symbol mod all prime factors, and only half of elements mod a prime have positive Jacobi symbol). If n is not in a two-prime-product structure then it is certainly not a Blum integer. Omitting details, for any group element of positive Jacobi symbol mod such n (which is non-Blum and non-square), a prover will have at most a 50% chance of correctly demonstrating the above. Clearly, such a proof using k random challenges will result in an error probability bounded by ½k, which approaches zero much faster than e−k/74. (See the comparison between them in the previous paragraph).
The simplest way to show quadratic residue evidence to display a square root of a quadratic residue. In the protocol of Van de Graaf and Peralta for proving Blum integer, the verifier should check that the Jacobi symbol of a square root of a random challenge comply with a pre-agreed random sign. This follows Blum's observation that if n is a Blum integer, then any quadratic residue has square roots of positive and negative Jacobi symbols [M. Blum. Coin flipping by telephone: a protocol for solving impossible problems, Proceedings of 24th IEEE Computer Conference (CompCon(, 1982, pp. 133–137.]. In the protocol of Gennaro et al [R. Gennaro, D. Miccianicio and T. Rabin. An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, In 5th ACM Conference on Computer and Communications Security, October 1998.], a verifier should require that for each challenge g sent as challenge, a square root of either ±g or ±2g mod n will be replied. It is possible for a prover to correctly respond to such challenges if one of the prime factors of n is congruent to 5 mod 8, and the other to 7 mod 8. These form an additional constraint to n being a Blum integer.
Note that two different square roots of a quadratic residue mod n can lead to factoring n with a non-trivial probability. So it will be dangerous for a prover to disclose a square root of a challenge which is solely selected by the verifier. The two protocols in R. Gennaro, D. Miccianicio and T. Rabin. An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, In 5th ACM Conference on Computer and Communications Security, October 1998 J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public-key, Advances in Cryptology—Proceedings of CRYPTO 87 (E. Pomerance, ed.), Lecture Notes in Computer Science, Springer-Verlag 293 (1988), pp. 128–134 assume the existence of mutually trusted random source which is accessible be the prover and verifier. The applicant believes that it will be costly to implement a mutually trusted random source between two mutually untrusted parties. The cost can be estimated by a protocol that allows the two parties to generate mutually trusted random elements without using a trusted third party. Blum's idea of coin flipping [M. Blum. Coin flipping by telephone: a protocol for solving impossible problems, Proceedings of 24th IEEE Computer Conference (CompCon), 1982, pp. 133–137.] is such a protocol and is used by R. Berger, S. Kannan and R. Peralta. [A framework for the study of cryptographic protocols, Advances in Cryptology—Proceedings of CRYPTO 85 (H. C. Williams ed.), Lecture Notes in Computer Science, Springer-Verlag 218 (1986), pp. 87–103, Z. Galil, S. Haber and M. Yung. A private interactive test of a boolean predicate and minimum-knowledge public-key cryptosystems, 26th FOCS, 1985, pp. 360–371]. Each instantiation of that protocol generates a truly random bit. Each random challenge of size of n generated this way takes log2n iterations and the same number of multi-precision operations of integers mod n (evaluation of log2n Jacobi symbols). Together k log2n iterations are needed for merely agreeing on k mutually trusted random challenges.
Above we have analyzed the cost for the previous protocols to prove an integer in the two-prime-power structure, i.e., n=prss where p, q are distinct primes and r, s, integers. To further prove r=s=1 one can use the protocol of Boyar et al [J. Boyar, K. Friedl and C. Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies, Advances in Cryptology—Proceedings of EUROCRYPT 89 (J.-j. Quisquater and J. Vandewalle, eds.), Lecture Notes in Computer Science, Springer-Verlag 434 (1990), pp. 155–172.] for proving square-free integers. Furthermore, to show that p and q are roughly equal size one can use Damgard's method of “checking commitment” protocol [I. B. Damgard. Practical and provably secure release of a secret and exchange of signatures, Advances in Cryptology: Proceedings of EUROCRYPT 93 (T. Helleseth, ed.), Lecture Notes in Computer Science, Springer-Verlag, 765 (1994), pp. 201–217.]. However, the costs of applying these two additional protocols will be ignored because they are less expensive than that for proving the two-prime-power structure, in particular for the case of non-Blum integers.
Solovay and Strassen disclosed, in an article titled “A Fast Monte-Carlo Test for Primality” SIAM J. COMPUTING Vol 6, No 1, March 1977, an efficient Monte-Carlo test for determining the probability that a given odd integer n is prime. The probability that n is composite is   <            1      /              2        k              ⁢                  ⁢    if    ⁢                  ⁢          a                        (                      x            -            1                    )                /        2              ≡            (              a        x            )        ⁢          (              mod        ⁢                                  ⁢        x            )      for all of k random values of a<x, where   (      a    x    )is the Jacobi symbol of a mod x.
This “Solovay-Strassen” test can provide an efficient means for determining the probability that each of p and q are primes, where n=p.q, by submitting p and q to the test in turn. However, this requires p and q to be disclosed to the person verifying that n is product of two, only, primes.
To better understand the operation of the methods disclosed herein, the following terminology is used.
Let P be a positive integer. ZP* denotes the multiplicative group of elements mod P. For a∈ZP*, OrdP(a) denote the order of a mod P.
Let a and b be integers. a|b denotes a dividing b; (a, b) denotes the greatest common divisor of a and b;   (      a    b    )denotes the Jacobi symbol of a mod b; l(a) denotes the size of a, which is the number of the bits in the binary representation of a.
Let x be a real number. └x┘ denotes the integer part of x (thus l(a)=└log2(a)┘+1); |x| denotes the absolute value of x.
Let S be a set. #S denotes the cardinality of S.
Finally, Pr[E] denotes the probability for event E to occur.
The present applicant has determined that a Monte-Carlo test of the primality of a both of positive integers p and q, where n=p.q can comprise the following steps:                a) find a prime number P such that n|(P−1);        b) select any positive integer f such that A≠B, A≠1, B≠1 where                    A=gpmodP,            B=gqmodP, and            g=f(P−1)/nmodP;                        then repeatedly:        c) choose a random h∈Zn* and             (              h        n            )        =          -      1        ;        d) choose random positive integers u, v;        e) calculate, modP;                    HU=B(humod n);            HV=A(hvmod n);            r=u+(p−1)/2;            s=v+(q−1)/2;                        f) determine whether, modP,                    B(hrmod n)=HU±1; and            A(hsmod n)=HU∓1.                        
It can be seen that the results of a Solovay-Strassen primality test are obtained on both p and q by steps f) of this method. Furthermore, the applicant has determined that the difficulty of finding p and q from knowledge of n, A and B of this test is at least as difficult as solving the decision problem on the membership of the Diffe-Hellman quadruples generated by g. (This is assumes that factorization of n and computing discrete logarithms to the base g are infeasible). Thus, if a verifier could be convinced that a prover has provided values for step f) which are properly related to p, q and the value of h (supplied by the verifier), the verifier would equally be confident of the Solovay-Strassen primality test using those values provide.
The present invention is as claimed in the claims.